The computers, mobile devices, and cellular phones that we use every day are equipped with camera devices that record observations of the physical world. Lacking the power of human-like cognition however, these devices cannot quickly or reliably recognize ordinary objects or physical locations. To aid computing devices, a number of artificial patterns or visual data coding schemes have been introduced into our physical world. These patterns are called targets, markers, labels, and the like. These terms will be used interchangeably in this document.
A target that encodes data is called a fiducial marker. The most widespread fiducial marker is the 1-D bar code. When applied to an object, the bar code allows a computer to identify the object, and this information can be used to look up a price, track inventory, or bring up any appropriate information on the computer screen. We use the terms target and marker intermittently throughout the description.
While bar codes are designed to be detected by special coherent light scanners, many other fiducial markers have been developed based on 2-D patterns detectable by high-resolution Charged Coupled Device (CCD) cameras. Fiducials such as Data Matrix, utilized by the U.S. Postal Service and Maxicode, which is used by United Parcel Service, are commonly used for mail and package sorting. Another fiducial, Quick Response (QR) code, has been widely adopted for use in commercial tracking and has had recent popular appeal for mobile information tagging. These markers are designed to encode thousands of bits of information with data redundancy in a form that can be read by a CCD camera.
While fiducial markers are primarily concerned with encoding data, a related class of targets, augmented reality markers, are designed to encode identifying information and convey a 3-D position. These markers are designed to encode less data but be more recognizable in low-resolution images.
Yet another class of visual targets, photogrammetry targets, has been developed to derive precise positioning and measurement from images. Applications of the use of identifiable targets in photogrammetry include lens modeling and calibration, precise measurement, and optical positioning systems. In these applications, it is necessary to identify and precisely locate within a 2-D raster image the projection of identifiable targets placed in physical 3-D space.
Photogrammetry targets can be located within a 2-D image to a sub-pixel resolution. It is well known in the art that circular targets can very accurately locate points within an image, because circles project to near ellipses when viewed at any angle, even with distorted lenses, and the centers of these ellipses can be detected despite variations in light exposure level, contrast, and image blur. Coded photogrammetry targets convey an identifying code as well as precise positioning.
Photogrammetry targets exist in a few varieties:                1. Uncoded targets that convey position but not identification, e.g., a uniform circular dot.        2. Coded Photogrammetry targets that convey a precise location and identification data for the point.        3. Fixtures and scale bars that are precisely machined 3-D structures containing multiple locatable positions.        4. Photogrammetry target sheets containing multiple circular dots on a 2-D surface arranged in a configuration that is recognizable in an image after projection.Motivation for an Improved Target Design        
Applications of the existing target systems have been primarily for industrial and special purpose computer systems, in environments of controlled viewing angles and controlled lighting, and utilizing cameras with high quality lenses and high-resolution sensors.
There exists a need now, however, for the general ability to detect and precisely locate targets from mobile devices such as PDAs, cell phones, smart phones, and other devices not necessarily equipped with high quality lenses and high-resolution sensors. While these devices are programmable, they contain very limited, low cost camera systems. These cameras typically have poor quality fixed focus optics, low resolution sensors, and are often used in naturally lit and poorly lit environments.
In applications of fiducial tag reading, augmented reality, and photogrammetry, it is necessary that targets be identified at a wide range of viewing angles, and at a long range. Given the low resolution of mobile device cameras, this ability is limited primarily by the size of the target. What is needed is a target that can be identified and precisely located when occupying a minimum number of pixels in a poor quality captured image.
When observing patterns occupying only a few pixels, the distorting effects of low cost cameras on the image signal can be significant, and these effects must be mitigated to reliably detect and locate a compact pattern.
Deficiencies of the Existing Systems
The locating and identifying mechanisms of existing target designs are not suited for low-resolution, blurry, or distorted images. Because of many image distortions object shapes may be altered, boundary edges shift, and sharp corners become rounded. Low cost lens distortion can also cause straight lines to appear bent, and assumptions about projection to be inaccurate.
A number of methods utilize square corner detection, as this is easily accomplished with image processing techniques. These corner-based methods suffer from distortions to the image that happen as a result of exposure level, contrast, and image blur, ultimately making square corners a poor choice for determining an exact location. Squares are also difficult to recognize at a low resolution if an image becomes excessively blurred, as sharp features all tend to be rounded by the optical system, demosaicing, and image compression. Using the inaccurate corner positions causes any derived 3-D pose (full 3-D position and orientation) to be inaccurate as well.
Several existing targets surround a circular dot with coding information that allows it to be identified. Though able to convey a highly accurate position, these methods all suffer from the drawback that the identifying features require significantly more image area than the locating dot. The boundary shift effect can also make it difficult to locate the identifying features of many of these targets because the central dot may appear arbitrarily scaled.
Some systems use concentric features such as concentric circular rings and squares. The symmetry of these shapes can be easily detected and they convey a more reliable scale. However, these concentric features demand a significant amount of surface area without conveying a full 3-D pose.
Most existing targets use separate geometric features for conveying target location (or 3-D pose), and data encoding. The locating features are not able to encode any additional information (for example identification, coding scheme, or printed target scale).
Some methods determine pose based on oversimplified lens projection models. Some methods are able to estimate a 3-D pose but are not able to produce a metric for the reliability of that pose (for example, reprojection error).
Some targets produce only one high precision location, thus multiple coded targets are required to recognize a pose in three dimensions. This requires significantly more target area. Often these targets must be surveyed to find their locations relative to each other in 3-D space before they can be used to determine camera location.
Some targets arrange features such as dots or crosses in patterns such as lines, L's, or grids, as these patterns can be easily detected. Though able to convey multiple high accuracy locations, they require a significant number of dots, and they must be complex enough so they will not be confused with naturally occurring background patterns.
Other systems require three-dimensional targets to be constructed, or a precisely machined fixture to be utilized. These targets are simply too expensive and delicate for widespread use.
Yet other systems require use of specialized camera systems, laser, or optical systems. These systems are much more expensive than those that utilize low cost CCD cameras and are generally useful only in highly controlled environments.
The deficiencies of existing targets and locating systems can be summed us as follows:
a) Existing targets take up significant image area to encode identification while often locating only one high accuracy location.
b) Existing targets are not recognizable at extreme angles, or in low resolution or degraded images.
c) Most geometric features (and image area) of existing targets are not used for locating a position, but only for identification of the target.
d) Some systems require precisely machined three-dimensional targets.
e) Some systems require many targets to be surveyed before they can convey a 3-D pose.
f) Existing targets fail to compactly convey an accurate 3-D pose.